//给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。 
//
// 
//
// 示例： 
//
// 输入："Let's take LeetCode contest"
//输出："s'teL ekat edoCteeL tsetnoc"
// 
//
// 
//
// 提示： 
//
// 
// 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。 
// 
// Related Topics 字符串 
// 👍 255 👎 0

package com.leetcode.editor.cn;

//Java：反转字符串中的单词 III
class P557ReverseWordsInAStringIii {
    public static void main(String[] args) {
        Solution solution = new P557ReverseWordsInAStringIii().new Solution();
        // TO TEST
        String str = "Let's take LeetCode contest";
        String reverseWords = solution.reverseWords(str);
        System.out.println(reverseWords);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String reverseWords(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }
//            StringBuilder builder = new StringBuilder();
            //用空格分割字符串，遍历分割后的数组，分割后元素每个倒叙遍历
//            String[] split = s.split(" ");
//            for (String s1 : split) {
//                if (s1.length() != 0) {
//                    for (int i = s1.length() - 1; i >= 0; i--) {
//                        builder.append(s1.charAt(i));
//                    }
//                    builder.append(" ");
//                }
//            }
            //双指针
//            int length = s.length();
//            int pos = 0;
//            int start = 0;
//            while (pos < length) {
//                if (s.charAt(pos) != ' ') {
//                    pos++;
//                }else{
//                    for (int i = pos - 1; i >= start; i--) {
//                        builder.append(s.charAt(i));
//                    }
//                    builder.append(" ");
//                    start = ++pos;
//                }
//            }
//            if(start<length){
//                for (int i = pos - 1; i >= start; i--) {
//                    builder.append(s.charAt(i));
//                }
//            }
//            return builder.toString();
//            int length = s.length();//字符串长度
//            int i = 0;//字符串下标
//            while (i < length) {
//                int start = i;
//                while (i < length && s.charAt(i) != ' ') {//查找字符，遇到空格停止查找
//                    i++;
//                }
//                for (int p = start; p < i; p++) {
//                    builder.append(s.charAt(start + i - 1 - p));//将查找到的字符反转追加到新的字符序列中
//                }
//                while (i < length && s.charAt(i) == ' ') {
//                    i++;
//                    builder.append(' ');//追加空格
//                }
//            }
//            return builder.toString();
            //反转数组
            char[] chars = s.toCharArray();
            int length = chars.length;
            //双指针
            int pos = 0;
            int start = 0;
            while (pos < length) {
                if (chars[pos] != ' ') {
                    pos++;
                } else {
                    reverseArr(chars, start, pos - 1);
                    start = ++pos;
                }
            }
            if (start < length) {
                reverseArr(chars, start, length - 1);
            }
            return String.valueOf(chars);
        }

        //反转数组指定区间元素
        void reverseArr(char[] chars, int start, int end) {
            while (start < end) {
                char temp = chars[start];
                chars[start] = chars[end];
                chars[end] = temp;
                start++;
                end--;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}